Smooth Optimization for Effective Multiple Kernel Learning.

Online Multiple Kernel Learning Algorithms and Mistake Bounds.

The Research on Teaching Method of Basics Course of Computer based on Cluster Analysis.

Online visual vocabulary pruning using pairwise constraints.

Simple and Efficient Multiple Kernel Learning by Group Lasso.
We consider the problem of how to improve the efficiency of Multiple Kernel Learning (MKL). In literature, MKL is often solved by an alternating approach: (1) the minimization of the kernel weights is solved by complicated techniques, such as Semi-infinite Linear Programming, Gradient Descent, or Level method; (2) the maximization of SVM dual variables can be solved by standard SVM solvers. However, the minimization step in these methods is usually dependent on its solving techniques or commercial softwares, which therefore limits the efficiency and applicability. In this paper, we formulate a closed-form solution for optimizing the kernel weights based on the equivalence between group-lasso and MKL. Although this equivalence is not our invention, our derived variant equivalence not only leads to an efficient algorithm for MKL, but also generalizes to the case for Lp-MKL (p ≥ 1 and denoting the Lp-norm of kernel weights). Therefore, our proposed algorithm provides a unified solution for the entire family of Lp-MKL models. Experiments on multiple data sets show the promising performance of the proposed technique compared with other competitive methods. 1.
Learning from Noisy Side Information by Generalized Maximum Entropy Model.
We consider the problem of learning from noisy side information in the form of pairwise constraints. Although many algorithms have been developed to learn from side information, most of them assume perfect pairwise constraints. Given the pairwise constraints are often extracted from data sources such as paper citations, they tend to be noisy and inaccurate. In this paper, we introduce the generalization of maximum entropy model and propose a framework for learning from noisy side information based on the generalized maximum entropy model. The theoretic analysis shows that under certain assumption, theclassificationmodeltrainedfromthe noisy side information can be very close to theonetrainedfromthe perfectsideinformation. Extensive empirical studies verify the effectiveness of the proposed framework. 1.
Unsupervised Ensemble Ranking Application to Large%2DScale Image Retrieval.

Exploitation and exploration in a performance based contextual advertising system.

Unsupervised transfer classification application to text categorization.

Exploitation and exploration in a performance based contextual advertising system.

Directed Network Community Detection A Popularity and Productivity Link Model.
In this paper, we consider the problem of community detection in directed networks by using probabilistic models. Most existing probabilistic models for community detection are either symmetric in which incoming links and outgoing links are treated equally or conditional in which only one type (i.e., either incoming or outgoing) of links is modeled. We present a probabilistic model for directed network community detection that aims to model both incoming links and outgoing links simultaneously and differentially. In particular, we introduce latent variables node productivity and node popularity to explicitly capture outgoing links and incoming links, respectively. We demonstrate the generality of the proposed framework by showing that both symmetric models and conditional models for community detection can be derived from the proposed framework as special cases, leading to better understanding of the existing models. We derive efficient EM algorithms for computing the maximum likelihood solutions to the proposed models. Extensive empirical studies verify the effectiveness of the new models as well as the insights obtained from the unified framework.
Non%2Dparametric Mixture Models for Clustering.
Abstract. We generalize traditional goals of clustering towards distinguishing components in a non-parametric mixture model. The clusters are not necessarily based on point locations, but on higher order criteria. This framework can be implemented by embedding probability distributions in a Hilbert space. The corresponding clustering objective is very general and relates to a range of common clustering concepts. 1
Efficient Algorithm for Localized Support Vector Machine.

A Boosting Framework for Visuality%2DPreserving Distance Metric Learning and Its Application to Medical Image Retrieval.

Discriminative semi%2Dsupervised feature selection via manifold regularization.
We consider the problem of semi-supervised feature selection, where we are given a small amount of labeled examples and a large amount of unlabeled examples. Since a small number of labeled samples are usually insufficient for identifying the relevant features, the critical problem arising from semi-supervised feature selection is how to take advantage of the information underneath the unlabeled data. To address this problem, we propose a novel discriminative semi-supervised feature selection method based on the idea of manifold regularization. The proposed method selects features through maximizing the classification margin between different classes and simultaneously exploiting the geometry of the probability distribution that generates both labeled and unlabeled data. We formulate the proposed feature selection method into a convex-concave optimization problem, where the saddle point corresponds to the optimal solution. To find the optimal solution, the level method, a fairly recent optimization method, is employed. We also present a theoretic proof of the convergence rate for the application of the level method to our problem. Empirical evaluation on several benchmark data sets demonstrates the effectiveness of the proposed semi-supervised feature selection method. 1
First ACM SIGMM international workshop onsocial media %28WSM%2709%29.

On the Use of Dynamic Bayesian Networks in Reconstructing Functional Neuronal Networks from Spike Train Ensembles.

First ACM SIGMM international workshop onsocial media %28WSM%2709%29.

Distance metric learning from uncertain side information with application to automated photo tagging.

Learning a distance metric from multi%2Dinstance multi%2Dlabel data.
Multi-instance multi-label learning (MIML) refers to the learning problems where each example is represented by a bag/collection of instances and is labeled by multiple labels. An example application of MIML is visual object recognition in which each image is represented by multiple key points (i.e., instances) and is assigned to multiple object categories. In this paper, we study the problem of learning a distance metric from multi-instance multi-label data. It is significantly more challenging than the conventional setup of distance metric learning because it is difficult to associate instances in a bag with its assigned class labels. We propose an iterative algorithm for MIML distance metric learning: it first estimates the association between instances in a bag and its assigned class labels, and learns a distance metric from the estimated association by a discriminative analysis; the learned metric will be used to update the association between instances and class labels, which is further used to improve the learning of distance metric. We evaluate the proposed algorithm by the task of automated image annotation, a well known MIML problem. Our empirical study shows an encouraging result when combining the proposed algorithm with citation-kNN, a state-of-theart algorithm for multi-instance learning. 1.
Inferring functional cortical networks from spike train ensembles using Dynamic Bayesian Networks.

Content%2Dbased image retrieval An application to tattoo images.
Tattoo images on human body have been routinely collected and used in law enforcement for suspect and victim identification. However, the current practice of matching
Non%2Dmonotonic feature selection.
We consider the problem of selecting a subset of m most informative features where m is the number of required features. This feature selection problem is essentially a combinatorial optimization problem, and is usually solved by an approximation. Conventional feature selection methods address the computational challenge in two steps: (a) ranking all the features by certain scores that are usually computed independently from the number of specified features m, and (b) selecting the top m ranked features. One major shortcoming of these approaches is that if a feature f is chosen when the number of specified features is m, it will always be chosen when the number of specified features is larger than m. We refer to this property as the “monotonic ” property of feature selection. In this work, we argue that it is important to develop efficient algorithms for non-monotonic feature selection. To this end, we develop an algorithm for non-monotonic feature selection that approximates the related combinatorial optimization problem by a Multiple Kernel Learning (MKL) problem. We also present a strategy that derives a discrete solution from the approximate solution of MKL, and show the performance guarantee for the derived discrete solution when compared to the global optimal solution for the related combinatorial optimization problem. An empirical study with a number of benchmark data sets indicates the promising per-
Online learning by ellipsoid method.
In this work, we extend the ellipsoid method, which was originally designed for convex optimization, for online learning. The key idea is to approximate by an ellipsoid the classification hypotheses that are consistent with all the training examples received so far. This is in contrast to most online learning algorithms where only a single classifier is maintained at each iteration. Efficient algorithms are presented for updating both the centroid and the positive definite matrix of ellipsoid given a misclassified example. In addition to the classical ellipsoid method, an improved version for online learning is also presented. Mistake bounds for both ellipsoid methods are derived. Evaluation with the USPS dataset and three UCI data-sets shows encouraging results when comparing the proposed online learning algorithm to two state-of-the-art online learners. 1.
Discriminative Semi%2DSupervised Feature Selection via Manifold Regularization.
We consider the problem of semi-supervised feature selection, where we are given a small amount of labeled examples and a large amount of unlabeled examples. Since a small number of labeled samples are usually insufficient for identifying the relevant features, the critical problem arising from semi-supervised feature selection is how to take advantage of the information underneath the unlabeled data. To address this problem, we propose a novel discriminative semi-supervised feature selection method based on the idea of manifold regularization. The proposed method selects features through maximizing the classification margin between different classes and simultaneously exploiting the geometry of the probability distribution that generates both labeled and unlabeled data. We formulate the proposed feature selection method into a convex-concave optimization problem, where the saddle point corresponds to the optimal solution. To find the optimal solution, the level method, a fairly recent optimization method, is employed. We also present a theoretic proof of the convergence rate for the application of the level method to our problem. Empirical evaluation on several benchmark data sets demonstrates the effectiveness of the proposed semi-supervised feature selection method. 1
Combining link and content for community detection a discriminative approach.

A Bayesian Approach Toward Finding Communities and Their Evolutions in Dynamic Social Networks.

Semisupervised SVM batch mode active learning with applications to image retrieval.



Batch Mode Active Learning with Applications to Text Categorization and Image Retrieval.
Abstract—Most machine learning tasks in data classification and information retrieval require manually labeled data examples in the training stage. The goal of active learning is to select the most informative examples for manual labeling in these learning tasks. Most of the previous studies in active learning have focused on selecting a single unlabeled example in each iteration. This could be inefficient, since the classification model has to be retrained for every acquired labeled example. It is also inappropriate for the setup of information retrieval tasks where the user’s relevance feedback is often provided for the top K retrieved items. In this paper, we present a framework for batch mode active learning, which selects a number of informative examples for manual labeling in each iteration. The key feature of batch mode active learning is to reduce the redundancy among the selected examples such that each example provides unique information for model updating. To this end, we employ the Fisher information matrix as the measurement of model uncertainty, and choose the set of unlabeled examples that can efficiently reduce the Fisher information of the classification model. We apply our batch mode active learning framework to both text categorization and image retrieval. Promising results show that our algorithms are significantly more effective than the active learning approaches that select unlabeled examples based only on their informativeness for the classification model. Index Terms—Batch mode active learning, logistic regressions, kernel logistic regressions, convex optimization, text categorization, image retrieval. Ç 1
SemiBoost Boosting for Semi%2DSupervised Learning.
Semi-supervised learning has attracted a significant amount of attention in pattern recognition and machine learning. Most previous studies have focused on designing special algorithms to effectively exploit the unlabeled data in conjunction with labeled data. Our goal is to improve the classification accuracy of any given supervised learning algorithm by using the available unlabeled examples. We call this as the Semi-supervised improvement problem, to distinguish the proposed approach from the existing approaches. We design a meta-semi-supervised learning algorithm that wraps around the underlying supervised algorithm, and improves its performance using unlabeled data. This problem is particularly important when we need to train a supervised learning algorithm with a limited number of labeled examples and a multitude of unlabeled examples. We present a boosting framework for semi-supervised learning, termed as SemiBoost. The key advantages of the proposed semi-supervised learning approach are: (a) performance improvement of any supervised learning algorithm with a multitude of unlabeled data, (b) efficient computation by the iterative boosting algorithm, and (c) exploiting both manifold and cluster assumption in training classification models. An empirical study on 16 different datasets, and on text categorization demonstrates that the proposed framework improves the performance of several commonly used supervised learning algorithms, given a large number of unlabeled examples. We also show that the performance of the proposed algorithm, SemiBoost, is comparable to the state-ofthe-art semi-supervised learning algorithms. 
Identifying Functional Connectivity in Large%2DScale Neural Ensemble Recordings A Multiscale Data Mining Approach.

Semi%2DSupervised Ensemble Ranking.
Ranking plays a central role in many Web search and information retrieval applications. Ensemble ranking, sometimes called meta-search, aims to improve the retrieval performance by combining the outputs from multiple ranking algorithms. Many ensemble ranking approaches employ supervised learning techniques to learn appropriate weights for combining multiple rankers. The main shortcoming with these approaches is that the learned weights for ranking algorithms are query independent. This is suboptimal since a ranking algorithm could perform well for certain queries but poorly for others. In this paper, we propose a novel semi-supervised ensemble ranking (SSER) algorithm that learns query-dependent weights when combining multiple rankers in document retrieval. The proposed SSER algorithm is formulated as an SVM-like quadratic program (QP), and therefore can be solved efficiently by taking advantage of optimization techniques that were widely used in existing SVM solvers. We evaluated the proposed technique on a standard document retrieval testbed and observed encouraging results by comparing to a number of state-of-the-art techniques.
Using Knowledge Driven Matrix Factorization to Reconstruct Modular Gene Regulatory Network.
Reconstructing gene networks from micro-array data can provide information on the mechanisms that govern cellular processes. Numerous studies have been devoted to addressing this problem. A popular method is to view the gene network as a Bayesian inference network, and to apply structure learning methods to determine the topology of the gene network. There are, however, several shortcomings with the Bayesian structure learning approach for reconstructing gene networks. They include high computational cost associated with analyzing a large number of genes and inefficiency in exploiting prior knowledge of co-regulation that could be derived from Gene Ontology (GO) information. In this paper, we present a knowledge driven matrix factorization (KMF) framework for reconstructing modular gene networks that addresses these shortcomings. In KMF, gene expression data is initially used to estimate the correlation matrix. The gene modules and the interactions among the modules are derived by factorizing the correlation matrix. The prior knowledge in GO is integrated into matrix factorization to help identify the gene modules. An alternating optimization algorithm is presented to efficiently find the solution. Experiments show that our algorithm performs significantly better in identifying gene modules than several state-of-the-art algorithms, and the interactions among the modules uncovered by our algorithm are proved to be biologically meaningful.
Representative entry selection for profiling blogs.

Semi%2Dsupervised text categorization by active search.

Rank%2Dbased distance metric learning An application to image retrieval.

Semi%2Dsupervised SVM batch mode active learning for image retrieval.
Active learning has been shown as a key technique for improving content-based image retrieval (CBIR) performance. Among various methods, support vector machine (SVM) active learning is popular for its application to relevance feedback in CBIR. However, the regular SVM active learning has two main drawbacks when used for relevance feedback. First, SVM often suffers from learning with a small number of labeled examples, which is the case in relevance feedback. Second, SVM active learning usually does not take into account the redundancy among examples, and therefore could select multiple examples in relevance feedback that are similar (or even identical) to each other. In this paper, we propose a novel scheme that exploits both semi-supervised kernel learning and batch mode active learning for relevance feedback in CBIR. In particular, a kernel function is first learned from a mixture of labeled and unlabeled examples. The kernel will then be used to effectively identify the informative and diverse examples for active learning via a min-max framework. An empirical study with relevance feedback of CBIR showed that the proposed scheme is significantly more effective than other state-of-the-art approaches. 1.
Unifying discriminative visual codebook generation with classifier training for object category recognition.
The idea of representing images using a bag of visual words is currently popular in object category recognition. Since this representation is typically constructed using unsupervised clustering, the resulting visual words may not capture the desired information. Recent work has explored the construction of discriminative visual codebooks that explicitly consider object category information. However, since the codebook generation process is still disconnected from that of classifier training, the set of resulting visual words, while individually discriminative, may not be those best suited for the classifier. This paper proposes a novel optimization framework that unifies codebook generation with classifier training. In our approach, each image feature is encoded by a sequence of “visual bits ” optimized
Semi%2DSupervised Boosting for Multi%2DClass Classification.
Abstract. Most semi-supervised learning algorithms have been designed for binary classification, and are extended to multi-class classification by approaches such as one-against-the-rest. The main shortcoming of these approaches is that they are unable to exploit the fact that each example is only assigned to one class. Additional problems with extending semisupervised binary classifiers to multi-class problems include imbalanced classification and different output scales of different binary classifiers. We propose a semi-supervised boosting framework, termed Multi-Class Semi-Supervised Boosting (MCSSB), that directly solves the semisupervised multi-class learning problem. Compared to the existing semisupervised boosting methods, the proposed framework is advantageous in that it exploits both classification confidence and similarities among examples when deciding the pseudo-labels for unlabeled examples. Empirical study with a number of UCI datasets shows that the proposed MCSSB algorithm performs better than the state-of-the-art boosting algorithms for semi-supervised learning. Key words: Semi-supervised learning, Multi-Class Classification, Boosting 1
Active kernel learning.
Identifying the appropriate kernel function/matrix for a given dataset is essential to all kernel-based learning techniques. A number of kernel learning algorithms have been proposed to learn kernel functions or matrices from side information (e.g., either labeled examples or pairwise constraints). However, most previous studies are limited to “passive” kernel learning in which side information is provided beforehand. In this paper we present a framework of Active Kernel Learning (AKL) that actively identifies the most informative pairwise constraints for kernel learning. The key challenge of active kernel learning is how to measure the informativeness of an example pair given its class label is unknown. To this end, we propose a min-max approach for active kernel learning that selects the example pair that results in a large classification margin regardless of its assigned class label. We furthermore approximate the related optimization problem into a convex programming problem. We evaluate the effectiveness of the proposed algorithm by comparing it to two other implementations of active kernel learning. Empirical study with nine datasets on semi-supervised data clustering shows that the proposed algorithm is more effective than its competitors.
Active query selection for semi%2Dsupervised clustering.

An Extended Level Method for Efficient Multiple Kernel Learning.



Multi%2Dlabel Multiple Kernel Learning.
We present a multi-label multiple kernel learning (MKL) formulation in which the data are embedded into a low-dimensional space directed by the instancelabel correlations encoded into a hypergraph. We formulate the problem in the kernel-induced feature space and propose to learn the kernel matrix as a linear combination of a given collection of kernel matrices in the MKL framework. The proposed learning formulation leads to a non-smooth min-max problem, which can be cast into a semi-infinite linear program (SILP). We further propose an approximate formulation with a guaranteed error bound which involves an unconstrained convex optimization problem. In addition, we show that the objective function of the approximate formulation is differentiable with Lipschitz continuous gradient, and hence existing methods can be employed to compute the optimal solution efficiently. We apply the proposed formulation to the automated annotation of Drosophila gene expression pattern images, and promising results have been reported in comparison with representative algorithms. 1
Ranking refinement and its application to information retrieval.
We consider the problem of ranking refinement, i.e., to improve the accuracy of an existing ranking function with a small set of labeled instances. We are, particularly, interested in learning a better ranking function using two complementary sources of information, ranking information given by the existing ranking function (i.e., the base ranker) and that obtained from users ’ feedbacks. This problem is very important in information retrieval where feedbacks are gradually collected. The key challenge in combining the two sources of information arises from the fact that the ranking information presented by the base ranker tends to be imperfect and the ranking information obtained from users’ feedbacks tends to be noisy. We present a novel boosting algorithm for ranking refinement that can effectively leverage the uses of the two sources of information. Our empirical study shows that the proposed algorithm is effective for ranking refinement, and furthermore it significantly outperforms the baseline algorithms that incorporate the outputs from the base ranker as an additional feature.
Automated annotation of Drosophila gene expression patterns using a controlled vocabulary.

A Bayesian framework for knowledge driven regression model in micro%2Darray data analysis.

Active Algorithm Selection.
We present an integrated dual approach to reduce power consumption in infrastructure-mode 802.11 wireless LANs. A novel distributed power control algorithm adaptively adjusts the transmit power of the 802.11 radio/NIC to achieve power savings in the presence of mobility and RF noise. An adaptive radio activation algorithm selectively sleeps the 802.11 radio/NIC to reduce idle power consumption. We analyze the performance of these algorithms in an 802.11 testbed using Web traces of HTTP/TCP user data accesses. Our application-level architecture integrates the two approaches into an incrementally deployable and application-transparent solution for power management of the RF interface on 802.11-enabled laptops.
Semi%2DSupervised Learning by Mixed Label Propagation.

Automated Vocabulary Acquisition and Interpretation in Multimodal Conversational Systems.
Motivated by psycholinguistic findings that eye gaze is tightly linked to human language production, we developed an unsupervised approach based on translation models to automatically learn the mappings between words and objects on a graphic display during human machine conversation. The experimental results indicate that user eye gaze can provide useful information to establish such mappings, which have important implications in automatically acquiring and interpreting user vocabularies for conversational systems. 1
Discriminative Cluster Refinement Improving Object Category Recognition Given Limited Training Data.
A popular approach to problems in image classification is to represent the image as a bag of visual words and then employ a classifier to categorize the image. Unfortunately, a significant shortcoming of this approach is that the clustering and classification are disconnected. Since the clustering into visual words is unsupervised, the representation does not necessarily capture the aspects of the data that are most useful for classification. More seriously, the semantic relationship between clusters is lost, causing the overall classification performance to suffer. We introduce “discriminative cluster refinement” (DCR), a method that explicitly models the pairwise relationships between different visual words by exploiting their co-occurrence information. The assigned class labels are used to identify the co-occurrence patterns that are most informative for object classification. DCR employs a maximum-margin approach to generate an optimal kernel matrix for classification. One important benefit of DCR is that it integrates smoothly into existing bag-of-words information retrieval systems by employing the set of visual words generated by any clustering method. While DCR could improve a broad class of information retrieval systems, this paper focuses on object category recognition. We present a direct comparison with a state-of-the art method on the PASCAL 2006 database and show that cluster refinement results in a significant improvement in classification accuracy given a small number of training examples. 1.
Semi%2Dsupervised Collaborative Text Classification.

Learning nonparametric kernel matrices from pairwise constraints.
Many kernel learning methods have to assume parametric forms for the target kernel functions, which significantly limits the capability of kernels in fitting diverse patterns. Some kernel learning methods assume the target kernel matrix to be a linear combination of parametric kernel matrices. This assumption again importantly limits the flexibility of the target kernel matrices. The key challenge with nonparametric kernel learning arises from the difficulty in linking the nonparametric kernels to the input patterns. In this paper, we resolve this problem by introducing the graph Laplacian of the observed data as a regularizer when optimizing the kernel matrix with respect to the pairwise constraints. We formulate the problem into Semi-Definite Programs (SDP), and propose an efficient algorithm to solve the SDP problem. The extensive evaluation on clustering with pairwise constraints shows that the proposed nonparametric kernel learning method is more effective than other state-of-the-art kernel learning techniques. 1.
Design and Implementation of an Open Programmable Router Compliant to IETF ForCES Specifications.

A learning framework using Green%27s function and kernel regularization with application to recommender system.

BoostCluster boosting clustering by pairwise constraints.
Data clustering is an important task in many disciplines. A large number of studies have attempted to improve clustering by using the side information that is often encoded as pairwise constraints. However, these studies focus on designing special clustering algorithms that can effectively exploit the pairwise constraints. We present a boosting framework for data clustering, termed as BoostCluster, that is able to iteratively improve the accuracy of any given clustering algorithm by exploiting the pairwise constraints. The key challenge in designing a boosting framework for data clustering is how to influence an arbitrary clustering algorithm with the side information since clustering algorithms by definition are unsupervised. The proposed framework addresses this problem by dynamically generating new data representations at each iteration that are, on the one hand, adapted to the clustering results at previous iterations by the given algorithm, and on the other hand consistent with the given side information. Our empirical study shows that the proposed boosting framework is effective in improving the performance of a number of popular clustering algorithms (Kmeans, partitional SingleLink, spectral clustering), and its performance is comparable to the state-of-the-art algorithms for data clustering with side information.
Efficient Convex Relaxation for Transductive Support Vector Machine.
We consider the problem of Support Vector Machine transduction, which involves a combinatorial problem with exponential computational complexity in the number of unlabeled examples. Although several studies are devoted to Transductive SVM, they suffer either from the high computation complexity or from the solutions of local optimum. To address this problem, we propose solving Transductive SVM via a convex relaxation, which converts the NP-hard problem to a semi-definite programming. Compared with the other SDP relaxation for Transductive SVM, the proposed algorithm is computationally more efficient with the number of free parameters reduced from O(n 2) to O(n) where n is the number of examples. Empirical study with several benchmark data sets shows the promising performance of the proposed algorithm in comparison with other state-of-the-art implementations of Transductive SVM. 1
Tattoo%2DID Automatic Tattoo Image Retrieval for Suspect and Victim Identification.

Localized Support Vector Machine and Its Efficient Algorithm.
kernel functions to classify data sets with complex decision surfaces. Determining the right parameters of such functions is not only computationally expensive, the resulting models are also susceptible to overfitting due to their large VC dimensions. Instead of fitting a nonlinear model, this paper presents a framework called Localized Support Vector Machine (LSVM), which builds multiple linear SVM models from the training data. Since each model is designed to classify a particular test example, it has high computational cost. To overcome this limitation, we propose an efficient implementation of LSVM, termed Profile SVM (PSVM). PSVM partitions the training examples into clusters and builds a separate linear SVM model for each cluster. Our empirical results show that (1) Both LSVM and PSVM outperform nonlinear SVM on the majority of the evaluated data sets; and (2) PSVM achieves comparable accuracy as LSVM but with significant computational savings. 1
Similarity Beyond Distance Measurement.

Localized Support Vector Machine and Its Efficient Algorithm.
kernel functions to classify data sets with complex decision surfaces. Determining the right parameters of such functions is not only computationally expensive, the resulting models are also susceptible to overfitting due to their large VC dimensions. Instead of fitting a nonlinear model, this paper presents a framework called Localized Support Vector Machine (LSVM), which builds multiple linear SVM models from the training data. Since each model is designed to classify a particular test example, it has high computational cost. To overcome this limitation, we propose an efficient implementation of LSVM, termed Profile SVM (PSVM). PSVM partitions the training examples into clusters and builds a separate linear SVM model for each cluster. Our empirical results show that (1) Both LSVM and PSVM outperform nonlinear SVM on the majority of the evaluated data sets; and (2) PSVM achieves comparable accuracy as LSVM but with significant computational savings. 1


An empirical investigation of user term feedback in text%2Dbased targeted image search.

Multi%2DClass Learning by Smoothed Boosting.

Identifying neuronal assemblies with local and global connectivity with scale space spectral clustering.

An Efficient Algorithm for Local Distance Metric Learning.
Learning application-specific distance metrics from labeled data is critical for both statistical classification and information retrieval. Most of the earlier work in this area has focused on finding metrics that simultaneously optimize compactness and separability in a global sense. Specifically, such distance metrics attempt to keep all of the data points in each class close together while ensuring that data points from different classes are separated. However, particularly when classes exhibit multimodal data distributions, these goals conflict and thus cannot be simultaneously satisfied. This paper proposes a Local Distance Metric (LDM) that aims to optimize local compactness and local separability. We present an efficient algorithm that employs eigenvector analysis and bound optimization to learn the LDM from training data in a probabilistic framework. We demonstrate that LDM achieves significant improvements in both classification and retrieval accuracy compared to global distance learning and kernel-based KNN.
Semi%2Dsupervised Multi%2Dlabel Learning by Constrained Non%2Dnegative Matrix Factorization.
We present a novel framework for multi-label learning that explicitly addresses the challenge arising from the large number of classes and a small size of training data. The key assumption behind this work is that two examples tend to have large overlap in their assigned class memberships if they share high similarity in their input patterns. We capitalize this assumption by first computing two sets of similarities, one based on the input patterns of examples, and the other based on the class memberships of the examples. We then search for the optimal assignment of class memberships to the unlabeled data that minimizes the difference between these two sets of similarities. The optimization problem is formulated as a constrained Non-negative Matrix Factorization (NMF) problem, and an algorithm is presented to efficiently find the solution. Compared to the existing approaches for multi-label learning, the proposed approach is advantageous in that it is able to explore both the unlabeled data and the correlation among different classes simultaneously. Experiments with text categorization show that our approach performs significantly better than several state-of-the-art classification techniques when the number of classes is large and the size of training data is small.
Semi%2Dsupervised Multi%2Dlabel Learning by Constrained Non%2Dnegative Matrix Factorization.
We present a novel framework for multi-label learning that explicitly addresses the challenge arising from the large number of classes and a small size of training data. The key assumption behind this work is that two examples tend to have large overlap in their assigned class memberships if they share high similarity in their input patterns. We capitalize this assumption by first computing two sets of similarities, one based on the input patterns of examples, and the other based on the class memberships of the examples. We then search for the optimal assignment of class memberships to the unlabeled data that minimizes the difference between these two sets of similarities. The optimization problem is formulated as a constrained Non-negative Matrix Factorization (NMF) problem, and an algorithm is presented to efficiently find the solution. Compared to the existing approaches for multi-label learning, the proposed approach is advantageous in that it is able to explore both the unlabeled data and the correlation among different classes simultaneously. Experiments with text categorization show that our approach performs significantly better than several state-of-the-art classification techniques when the number of classes is large and the size of training data is small.
Correlated Label Propagation with Application to Multi%2Dlabel Learning.
Many computer vision applications, such as scene analysis and medical image interpretation, are ill-suited for traditional classification where each image can only be associated with a single class. This has stimulated recent work in multi-label learning where a given image can be tagged with multiple class labels. A serious problem with existing approaches is that they are unable to exploit correlations between class labels. This paper presents a novel framework for multi-label learning termed Correlated Label Propagation (CLP) that explicitly models interactions between labels in an efficient manner. As in standard label propagation, labels attached to training data points are propagated to test data points; however, unlike standard algorithms that treat each label independently, CLP simultaneously co-propagates multiple labels. Existing work eschews such an approach since naive algorithms for label co-propagation are intractable. We present an algorithm based on properties of submodular functions that efficiently finds an optimal solution. Our experiments demonstrate that CLP leads to significant gains in precision/recall against standard techniques on two real-world computer vision tasks involving several hundred labels. 1
Batch mode active learning and its application to medical image classification.
The goal of active learning is to select the most informative examples for manual labeling. Most of the previous studies in active learning have focused on selecting a single unlabeled example in each iteration. This could be inefficient since the classification model has to be retrained for every labeled example. In this paper, we present a framework for “batch mode active learning ” that applies the Fisher information matrix to select a number of informative examples simultaneously. The key computational challenge is how to efficiently identify the subset of unlabeled examples that can result in the largest reduction in the Fisher information. To resolve this challenge, we propose an efficient greedy algorithm that is based on the property of submodular functions. Our empirical studies with five UCI datasets and one realworld medical image classification show that the proposed batch mode active learning algorithm is more effective than the state-ofthe-art algorithms for active learning. 1.
Generalized Maximum Margin Clustering and Unsupervised Kernel Learning.

A graph%2Dbased framework for relation propagation and its application to multi%2Dlabel learning.

Large%2Dscale text categorization by batch mode active learning.
Large-scale text categorization is an important research topic for Web data mining. One of the challenges in large-scale text categorization is how to reduce the human efforts in labeling text documents for building reliable classification models. In the past, there have been many studies on applying active learning methods to automatic text categorization, which try to select the most informative documents for manually labeling. Most of these studies focused on selecting a single unlabeled document in each iteration. As a result, the text categorization model has to be retrained after each labeled document is solicited. In this paper, we present a novel active learning algorithm that selects a batch of text documents for manually labeling in each iteration. The key of the batch mode active learning is how to reduce the redundancy among the selected examples such that each example provides unique information for model updating. To this end, we use the Fisher information matrix as the measurement of model uncertainty and choose the set of documents that can efficiently minimize the Fisher information matrix of a classification model. Extensive experiments with three different datasets have shown that our algorithm is more effective than the state-of-the-art active learning techniques for text categorization and can be a promising tool toward large-scale text categorization on World Wide Web.
A statistical framework for query translation disambiguation.

A Unified Log%2DBased Relevance Feedback Scheme for Image Retrieval.
Abstract—Relevance feedback has emerged as a powerful tool to boost the retrieval performance in content-based image retrieval (CBIR). In the past, most research efforts in this field have focused on designing effective algorithms for traditional relevance feedback. Given that a CBIR system can collect and store users ’ relevance feedback information in a history log, an image retrieval system should be able to take advantage of the log data of users ’ feedback to enhance its retrieval performance. In this paper, we propose a unified framework for log-based relevance feedback that integrates the log of feedback data into the traditional relevance feedback schemes to learn effectively the correlation between low-level image features and high-level concepts. Given the error-prone nature of log data, we present a novel learning technique, named Soft Label Support Vector Machine, to tackle the noisy data problem. Extensive experiments are designed and conducted to evaluate the proposed algorithms based on the COREL image data set. The promising experimental results validate the effectiveness of our log-based relevance feedback scheme empirically. Index Terms—Content-based image retrieval, relevance feedback, log-based relevance feedback, log data, user issues, semantic gap, support vector machines.
A study of mixture models for collaborative filtering.

Collaborative image retrieval via regularized metric learning.
In content-based image retrieval (CBIR), relevant images are identified based on their similarities to query images. Most CBIR algorithms are hindered by the semantic gap between the low-level image features used for computing image similarity and the high-level semantic concepts conveyed in images. One way to reduce the semantic gap is to utilize the log data of users ’ feedback that has been collected by CBIR systems in history, which is also called “collaborative image retrieval”. In this paper, we present a novel metric learning approach, named “regularized metric learning”, for collaborative image retrieval, which learns a distance metric by exploring the correlation between low-level image features and the log data of users ’ relevance judgments. Compared to the previous research, a regularization mechanism is used in our algorithm to effectively prevent overfitting. Meanwhile, we formulate the proposed learning algorithm into a semi-definite programming problem, which can be solved very efficiently by existing software packages and is scalable to the size of log data. An extensive set of experiments has been conducted to show that the new algorithm can substantially improve the retrieval accuracy of a baseline CBIR system using Euclidean distance metric, even with a modest amount of log data. The experiment also indicates that the new algorithm is more effective and more efficient than
Query Translation Disambiguation as Graph Partitioning.
Resolving ambiguity in the process of query translation is crucial to cross-language information retrieval when only a bilingual dictionary is available. In this paper we propose a novel approach for query translation disambiguation, named “spectral query translation model”. The proposed approach views the problem of query translation disambiguation as a graph partitioning problem. For a given query, a weighted graph is first created for all possible translations of query words based on the co-occurrence statistics of the translation words. The best translation of the query is then determined by the most strongly connected component within the graph. The proposed approach distinguishes from previous approaches in that the translations of all query words are estimated simultaneously. Furthermore, translation probabilities are introduced in the proposed approach to capture the uncertainty in translating queries. Empirical studies with TREC datasets have shown that the spectral query translation model achieves a relative 20%- 50 % improvement in cross-language information retrieval, compared to other approaches that also exploit word co-occurrence statistics for query translation disambiguation.
Learn to weight terms in information retrieval using category information.

Sensor Localization in an Obstructed Environment.
Abstract. Sensor localization can be divided into two categories: rangebased approaches, and rang-free approaches. Although range-based approaches tend to be more accurate than range-free approaches, they are more sensitive to errors in distance measurement. Despite of the efforts on recovering sensors ’ Euclidean coordinates from erroneous distance measurements, as will be illustrated in this paper, they are still prone to distance errors, particularly in an obstruction abundant environment. In this paper, we propose a new algorithm for sensor localization based on Multiscale Radio Transmission Power(MRTP). It gradually increases the scale level of transmission power, and the distance is determined by the minimal scale of received signals. Unlike the range-based approaches, which treat each measured distance as an approximation of the true one, in our new approach, the measured distance serves as a constraint that limits the feasible location of sensors. Our simulations have shown that the MRTP-based approach is able to provide accurate and robust estimation of location, especially in an area abundant in obstructions, where most current approaches fail to perform well. 1
Integrating User Feedback Log into Relevance Feedback by Coupled SVM for Content%2DBased Image Retrieval.
Relevance feedback has been shown as an important tool to boost the retrieval performance in content-based image retrieval. In the past decade, various algorithms have been proposed to formulate relevance feedback in contentbased image retrieval. Traditional relevance feedback techniques mainly carry out the learning tasks by focusing lowlevel visual features of image content with little consideration on log information of user feedback. However, from a long-term learning perspective, the user feedback log is one of the most important resources to bridge the semantic gap problem in image retrieval. In this paper we propose a novel technique to integrate the log information of user feedback into relevance feedback for image retrieval. Our algorithm’s construction is based on a coupled support vector machine which learns consistently with the two types of information: the low-level image content and the user feedback log. We present a mathematical formulation of the problem and develop a practical algorithm to solve the problem effectively. Experimental results show that our proposed scheme is effective and promising. 1.
Learn to weight terms in information retrieval using category information.

A smoothed boosting algorithm using probabilistic output codes.
AdaBoost.OC has shown to be an e#ective  method in boosting &#034;weak&#034; binary classifiers  for multi-class learning. It employs the Error  Correcting Output Code (ECOC) method to  convert a multi-class learning problem into a  set of binary classification problems, and applies  the AdaBoost algorithm to solve them  e#ciently. In this paper, we propose a new  boosting algorithm that improves the AdaBoost.
Learning with Labeled Sessions.

A Novel Approach to Model Generation for Heterogeneous Data Classification.
Ensemble methods such as bagging and boosting have been successfully applied to classification problems. Two important issues associated with an ensemble approach are: how to generate models to construct an ensemble, and how to combine them for classification. In this paper, we focus on the problem of model generation for heterogeneous data classification. If we could partition heterogeneous data into a number of homogeneous partitions, we will likely generate reliable and accurate classification models over the homogeneous partitions. We examine different ways of forming homogeneous subsets and propose a novel method that allows a data point to be assigned multiple times in order to generate homogeneous partitions for ensemble learning. We present the details of the new algorithm and empirical studies over the UCI benchmark datasets and datasets of image classification, and show that the proposed approach is effective for heterogeneous data classification. 1
Linguistic theories in efficient multimodal reference resolution an empirical investigation.
Multimodal conversational interfaces provide a natural means for users to communicate with computer systems through multiple modalities such as speech, gesture, and gaze. To build effective multimodal interfaces, understanding user multimodal inputs is important. Previous linguistic and cognitive studies indicate that user language behavior does not occur randomly, but rather follows certain linguistic and cognitive principles. Therefore, this paper investigates the use of linguistic theories in multimodal interpretation. In particular, we present a greedy algorithm that incorporates Conversation Implicature and Givenness Hierarchy for efficient multimodal reference resolution. Empirical studies indicate that this algorithm significantly reduces the complexity in multimodal reference resolution compared to a previous graph-matching approach. One major advantage of this greedy algorithm is that the prior linguistic and cognitive knowledge can be used to guide the search and significantly prune the search space. Because of its simplicity and generality, this approach has the potential to improve the robustness of interpretation and provide a more practical solution to multimodal input interpretation.
A Probabilistic Approach for Optimizing Spectral Clustering.
Spectral clustering enjoys its success in both data clustering and semisupervised learning. But, most spectral clustering algorithms cannot handle multi-class clustering problems directly. Additional strategies are needed to extend spectral clustering algorithms to multi-class clustering problems. Furthermore, most spectral clustering algorithms employ hard cluster membership, which is likely to be trapped by the local optimum. In this paper, we present a new spectral clustering algorithm, named “Soft Cut”. It improves the normalized cut algorithm by introducing soft membership, and can be efficiently computed using a bound optimization algorithm. Our experiments with a variety of datasets have shown the promising performance of the proposed clustering algorithm. 1
A Framework for Incorporating Class Priors into Discriminative Classification.
Abstract. Discriminative and generative methods provide two distinct approaches to machine learning classification. One advantage of generative approaches is that they naturally model the prior class distributions. In contrast, discriminative approaches directly model the conditional distribution of class given inputs, so the class priors are only implicitly obtained if the input density is known. In this paper, we propose a framework for incorporating class prior proportions into discriminative methods in order to improve their classification accuracy. The basic idea is to enforce that the distribution of class labels predicted on the test data by the discriminative model is consistent with the class priors. Therefore, the discriminative model has to not only fit the training data well but also predict class labels for the test data that are consistent with the class priors. Experiments on five different UCI datasets and one image database show that this framework is effective in improving the classification accuracy when the training data and the test data come from the same class proportions, even if the test data does not have exactly the same feature distribution as the training data. 1
Adjusting Mixture Weights of Gaussian Mixture Model via Regularized Probabilistic Latent Semantic Analysis.
Abstract. Mixture models, such as Gaussian Mixture Model, have been widely used in many applications for modeling data. Gaussian mixture model (GMM) assumes that data points are generated from a set of Gaussian models with the same set of mixture weights. A natural extension of GMM is the probabilistic latent semantic analysis (PLSA) model, which assigns different mixture weights for each data point. Thus, PLSA is more flexible than the GMM method. However, as a tradeoff, PLSA usually suffers from the overfitting problem. In this paper, we propose a regularized probabilistic latent semantic analysis model (RPLSA), which can properly adjust the amount of model flexibility so that not only the training data can be fit well but also the model is robust to avoid the overfitting problem. We conduct empirical study for the application of speaker identification to show the effectiveness of the new model. The experiment results on the NIST speaker recognition dataset indicate that the RPLSA model outperforms both the GMM and PLSA models substantially. The principle of RPLSA of appropriately adjusting model flexibility can be naturally extended to other applications and other type of mixture models. 1
Symmetric Statistical Translation Models for Automatic Image Annotation.

User term feedback in interactive text%2Dbased image retrieval.
Abstract — In this paper, we present a novel relevance feedback method for Content-Based Image Retrieval systems based on dynamic feature weights. The proposed method utilizes intracluster and inter-cluster information for representing the descriptive and discriminative properties of the features according to the labeled images by the user. Afterwards, feature weights are updated dynamically according to the user’s preferences for improving retrieval results. The proposed method has been thoroughly evaluated and selected results are illustrated in the paper. It is shown that, satisfactory improvements can be achieved with small number of iterations and labeled samples. Furthermore, it is a low-complex and flexible method that can be used on various databases and Content-Based Image Retrieval applications. Relevance feedback, content-based image retrieval, low-level features, feature weights. I.
A maximum coherence model for dictionary%2Dbased cross%2Dlanguage information retrieval.
One key to cross-language information retrieval is how to efficiently resolve the translation ambiguity of queries given their short length. This problem is even more challenging when only bilingual dictionaries are available, which is the focus of this paper. In the previous research of crosslanguage information retrieval using bilingual dictionaries, the word co-occurrence statistics is used to determine the most likely translations of queries. In this paper, we propose a novel statistical model, named “maximum coherence model”, which estimates the translation probabilities of query words that are consistent with the word co-occurrence statistics. Unlike the previous work, where a binary decision is made for the selection of translations, the new model maintains the uncertainty in translating query words when their sense ambiguity is difficult to resolve. Furthermore, this new model is able to estimate translations of multiple query words simultaneously. This is in contrast to many previous approaches where translations of individual query words are determined independently. Empirical studies with TREC datasets have shown that the maximum coherence model achieves a relative 10 %- 40 % improvement in cross-language information retrieval, comparing to other approaches that also use word co-occurrence statistics for sense disambiguation.
Study of cross lingual information retrieval using on%2Dline translation systems.

Effective automatic image annotation via a coherent language model and active learning.
Image annotations allow users to access a large image database with textual queries. There have been several studies on automatic image annotation utilizing machine learning techniques, which automatically learn statistical models from annotated images and apply them to generate annotations for unseen images. One common problem shared by most previous learning approaches for automatic image annotation is that each annotated word is predicated for an image independently from other annotated words. In this paper, we proposed a coherent language model for automatic image annotation that takes into account the word-toword correlation by estimating a coherent language model for an image. This new approach has two important advantages: 1) it is able to automatically determine the annotation length to improve the accuracy of retrieval results, and 2) it can be used with active learning to significantly reduce the required number of annotated image examples. Empirical studies with Corel dataset are presented to show the effectiveness of the coherent language model for automatic image annotation. Categories and Subject Descriptors
Unified filtering by combining collaborative filtering and content%2Dbased filtering via mixture model and exponential model.

Regularizing translation models for better automatic image annotation.
The goal of automatic image annotation is to automatically generate annotations for images to describe their content. In the past, statistical machine translation models have been successfully applied to automatic image annotation task [8]. It views the process of annotating images as a process of translating the content from a ‘visual language ’ to textual words. One problem with the existing translation models is that common words are usually associated with too many different image regions. As a result, uncommon words have little chance to be used for annotating images. Uncommon words are important for automatic image annotation because they are often used in the queries. In this paper, we propose two modified translation models for automatic image annotation, namely the normalized translation model and the regularized translation model, that specifically address the problem of common annotated words. The basic idea is to raise the number of blobs that are associated with uncommon words. The normalized translation model realizes this by scaling translation probabilities of different words with different factors. The same goal is achieved in the regularized translation model through the introduction of a special Dirichlet prior. Empirical study with the Corel dataset has shown that both two modified translation models outperform the original translation model and several existing approaches for automatic image annotation substantially.
MSU at ImageCLEF Cross Language and Interactive Image Retrieval.

SWITCH A Novel Approach to Ensemble Learning for Heterogeneous Data.

Robust feature induction for support vector machines.
The goal of feature induction is to automatically create nonlinear combinations of existing features as additional input features to improve classification accuracy. Typically, nonlinear features are introduced into a support vector machine (SVM) through a nonlinear kernel function. One disadvantage of such an approach is that the feature space induced by a kernel function is usually of high dimension and therefore will substantially increase the chance of over-fitting the training data. Another disadvantage is that nonlinear features are induced implicitly and therefore are difficult for people to understand which induced features are critical to the classification performance. In this paper, we propose a boosting-style algorithm that can explicitly induces important nonlinear features for SVMs. We present empirical studies with discussion to show that this approach is effective in improving classification accuracy for SVMs. The comparison with an SVM model using nonlinear kernels also indicates that this approach is effective and robust, particularly when the number of training data is small. 1.
Ordering patterns by combining opinions from multiple sources.
Pattern ordering is an important task in data mining because the number of patterns extracted by standard data mining algorithms often exceeds our capacity to manually analyze them. A standard approach for handling this problem is to rank the patterns according to an evaluation metric and then presents only the highest ranked patterns to the users. This approach may not be trivial due to the wide variety of metrics available, some of which may lead to conflicting ranking results. In this paper, we present an effective approach to address the pattern ordering problem by combining the rank information gathered from multiple sources. Although rank aggregation techniques have been developed for applications such as meta-search engines, they are not directly applicable to pattern ordering for two reasons. First, the techniques are mostly supervised, i.e., they require a sufficient amount of labeled data. Second, the objects to be ranked are assumed to be independent and identically distributed (i.i.d), an assumption that seldom holds in pattern ordering. The method proposed in this paper is an adaptation of the original Hedge algorithm, modified to work in an unsupervised learning setting. Techniques for addressing the i.i.d. violation in pattern ordering are also presented. Experimental results demonstrate that our unsupervised Hedge algorithm outperforms many alternative techniques such as those based on weighted average ranking and singular value decomposition.
An automatic weighting scheme for collaborative filtering.
Collaborative filtering identifies information interest of a particular user based on the information provided by other similar users. The memory-based approaches for collaborative filtering (e.g., Pearson correlation coefficient approach) identify the similarity between two users by comparing their ratings on a set of items. In these approaches, different items are weighted either equally or by some predefined functions. The impact of rating discrepancies among different users has not been taken into consideration. For example, an item that is highly favored by most users should have a smaller impact on the user-similarity than an item for which different types of users tend to give different ratings. Even though simple weighting methods such as variance weighting try to address this problem, empirical studies have shown that they are ineffective in improving the performance of collaborative filtering. In this paper, we present an optimization algorithm to automatically compute the weights for different items based on their ratings from training users. More specifically, the new weighting scheme will create a clustered distribution for user vectors in the item space by bringing users of similar interests closer and separating users of different interests more distant. Empirical studies over two datasets have shown that our new weighting scheme substantially improves the performance of the Pearson correlation coefficient method for collaborative filtering.
A study of methods for normalizing user ratings in collaborative filtering.
The goal of collaborative filtering is to make recommendations for a test user by utilizing the rating information of users who share interests similar to the test user. Because ratings are determined not only by user interests but also the rating habits of users, it is important to normalize ratings of different users to the same scale. In this paper, we compare two different normalization strategies for user ratings, namely the Gaussian normalization method and the decoupling normalization method. Particularly, we incorporated these two rating normalization methods into two collaborative filtering algorithms, and evaluated their effectiveness on the EachMovie dataset. The experiment results have shown that the decoupling method for rating normalization is more effective than the Gaussian normalization method in improving the performance of collaborative filtering algorithms.
A Bayesian Approach toward Active Learning for Collaborative Filtering.
Collaborative filtering is a useful technique for exploiting the preference patterns of a group of users to predict the utility of items for the active user. In general, the performance of collaborative filtering depends on the number of rated examples given by the active user. The more the number of rated examples given by the active user, the more accurate the predicted ratings will be. Active learning provides an effective way to acquire the most informative rated examples from active users. Previous work on active learning for collaborative filtering only considers the expected loss function based on the estimated model, which can be misleading when the estimated model is inaccurate. This paper takes one step further by taking into account of the posterior distribution of the estimated model, which results in more robust active learning algorithm. Empirical studies with datasets of movie ratings show that when the number of ratings from the active user is restricted to be small, active learning methods only based on the estimated model don’t perform well while the active learning method using the model distribution achieves substantially better performance. 1.
Negative pseudo%2Drelevance feedback in content%2Dbased video retrieval.
Video information retrieval requires a system to find information relevant to a query which may be represented simultaneously in di#erent ways through a text description, audio, still images and/or video sequences. We present a novel approach that uses pseudo-relevance feedback from retrieved items that are NOT similar to the query items without further inquiring user feedback. We provide insight into this approach using a statistical model and suggest a score combination scheme via posterior probability estimation. An evaluation on the 2002 TREC Video Track queries shows that this technique can improve video retrieval performance on a real collection. We believe that negative pseudo-relevance feedback shows great promise for very difficult multimedia retrieval tasks, especially when combined with other di#erent retrieval algorithms.
Collaborative filtering with decoupled models for preferences and ratings.
In this paper, we describe a new model for collaborative filtering. The motivation of this work comes from the fact that two users with very similar preferences on items may have very different rating schemes. For example, one user may tend to assign a higher rating to all items than another user. Unlike previous models of collaborative filtering, which determine the similarity between two users only based on their rating performance, our model treats the user&#039;s preferences on items separately from the user&#039;s rating scheme. More specifically, for each user, we build two separate models: a preference model capturing which items are favored by the user and a rating model capturing how the user would rate an item given the preference information. The similarity of two users is computed based on the underlying preference model, instead of the surface ratings. We compare the new model with several representative previous approaches on two data sets. Experiment results show that the new model outperforms all the previous approaches that are tested consistently on both data sets.
Multimedia Search with Pseudo%2Drelevance Feedback.
We present an algorithm for video retrieval that fuses the decisions of multiple retrieval agents in both text and image modalities. While the normalization and combination of evidence is novel, this paper emphasizes the successful use of negative pseudo-relevance feedback to improve image retrieval performance. Although we have not solved all problems in video information retrieval, the results are encouraging, indicating that pseudo-relevance feedback shows great promise for multimedia retrieval with very varied and errorful data. 1 Video Retrieval from Mixed Text and Image Queries In this paper, we present an algorithm for the task of video retrieval. A query, consisting of a text description plus images or video is posed against a video collection, and relevant shots are to be retrieved. Our system accomplishes this by fusing the retrieval results of multiple retrieval agents. The overall system can be decomposed into several agents, including a text-oriented retrieval agent, which is responsible for finding the text in the speech transcripts [4] and Video OCR [3], a
Information retrieval for OCR documents a content%2Dbased probabilistic correction model.

A New Pairwise Ensemble Approach for Text Classification.
Text classification, whether by topic or genre, is an important  task that contributes to text extraction, retrieval, summarization  and question answering. In this paper we present a new pairwise ensemble  approach, which uses pairwise Support Vector Machine (SVM) classifiers  as base classifiers and &#034;input-dependent latent variable&#034; method  for model combination. This new approach better captures the characteristics  of genre classification, including its heterogeneous nature. Our  experiments on two multi-genre collections and one topic-based classification  datasets show that the pairwise ensemble method outperforms  both boosting, which has been demonstrated as a powerful ensemble  approach, and Error-Correcting Output Codes (ECOC), which applies  pairwise-like classifiers for multiclass classification problems.
A Faster Iterative Scaling Algorithm for Conditional Exponential Model.
Conditional exponential model has been one of the widely used conditional models in machine learning field and improved iterative scaling (IIS) has been one of the major algorithms for finding the optimal parameters for the conditional exponential model. In this paper, we proposed a faster iterative algorithm named FIS that is able to find the optimal parameters faster than the IIS algorithm. The theoretical analysis shows that the proposed algorithm yields a tighter bound than the traditional IIS algorithm. Empirical studies on the text classification over three different datasets showed that the new iterative scaling algorithm converges substantially faster than both the IIS algorithm and the conjugate gradient algorithm (CG). Furthermore, we examine the quality of the optimal parameters found by each learning algorithm in the case of incomplete training. Experiments have shown that, when only a limited amount of computation is allowed (e.g. no convergence is achieved), the new algorithm FIS is able to obtain lower testing errors than both the IIS method and the CG method. 1.
Flexible Mixture Model for Collaborative Filtering.
This paper presents a flexible mixture model  (FMM) for collaborative filtering. FMM extends  existing partitioning/clustering algorithms for  collaborative filtering by clustering both users  and items together simultaneously without  assuming that each user and item should only  belong to a single cluster. Furthermore, with the  introduction of `preference&#039; nodes, the proposed  framework is able to explicitly model how users  rate items, which can vary dramatically, even  among the users with similar tastes on items.
Modified Logistic Regression An Approximation to SVM and Its Applications in Large%2DScale Text Categorization.
Logistic Regression (LR) has been widely used in statistics for many years, and has received extensive study in machine learning community recently due to its close relations to Support Vector Machines (SVM) and AdaBoost. In this paper, we use a modified version of LR to approximate the optimization of SVM by a sequence of unconstrained optimization problems. We prove that our approximation will converge to SVM, and propose an iterative algorithm called “MLR-CG ” which uses Conjugate Gradient as its inner loop. Multiclass version “MMLR-CG ” is also obtained after simple modifications. We compare the MLR-CG with SVMlight over different text categorization collections, and show that our algorithm is much more efficient than SVMlight when the number of training examples is very large. Results of the multiclass version MMLR-CG is also reported. 1.
Video retrieval using speech and image information.
Video contains multiple types of audio and visual information, which are difficult to extract, combine or trade-off in general video information retrieval. This paper provides an evaluation on the effects of different types of information used for video retrieval from a video collection. A number of different sources of information are present in most typical broadcast video collections and can be exploited for information retrieval. We will discuss the contributions of automatically recognized speech transcripts, image similarity matching, face detection and video OCR in the contexts of experiments performed as part of 2001 TREC Video Retrieval Track evaluation performed by the National Institute of Standards and Technology. For the queries used in this evaluation, image matching and video OCR proved to be the deciding aspects of video information retrieval.
Preference%2Dbased Graphic Models for Collaborative Filtering.
Collaborative filtering is a very useful general technique for exploiting the preference patterns of a group of users to predict the utility of items to a particular user. Previous research has studied several probabilistic graphic models for collaborative filtering with promising results. However, while these models have succeeded in capturing the similarity among users and items, none of them has considered the fact that users with similar interests in items can have very different rating patterns; some users tend to assign a higher rating to all items than other users. In this paper, we propose and study two new graphic models that address the distinction between user preferences and ratings. In one model, called the decoupled model, we introduce two different variables to decouple a user’s preferences from his/her ratings. In the other, called the preference model, we model the orderings of items preferred by a user, rather than the user’s numerical ratings of items. Empirical study over two datasets of movie ratings shows that, due to its appropriate modeling of the distinction between user preferences and ratings, the proposed decoupled model significantly outperforms all the five existing approaches that we compared with. The preference model, however, performs much worse than the decoupled model, suggesting that while explicit modeling of the underlying user preferences is very important for collaborative filtering, we can not afford ignoring the rating information completely. 1.
Web Image Retrieval Re%2DRanking with Relevance Model.
Web image retrieval is a challenging task that requires efforts from image processing, link structure analysis, and web text retrieval. Since content-based image retrieval is still considered very difficult, most current large-scale web image search engines exploit text and link structure to &#034;understand &#034; the content of the web images. However, local text information, such as caption, filenames and adjacent text, is not always reliable and informative. Therefore, global information should be taken into account when a web image retrieval system makes relevance judgment. In this paper, we propose a re-ranking method to improve web image retrieval by reordering the images retrieved from an image search engine. The re-ranking process is based on a relevance model, which is a probabilistic model that evaluates the relevance of the HTML document linking to the image, and assigns a probability of relevance. The experiment results showed that the re-ranked image retrieval achieved better performance than original web image retrieval, suggesting the effectiveness of the re-ranking method. The relevance model is learned from the Internet without preparing any training data and independent of the underlying algorithm  of the image search engines. The re-ranking process should be applicable to any image search engines with little effort.
Statistical approaches toward automatic title generation.

A language modeling framework for resource selection and results merging.
Statistical language models have been proposed recently for several information retrieval tasks, including the resource selection task in distributed information retrieval. This paper extends the language modeling approach to integrate resource selection, ad-hoc searching, and merging of results from different text databases into a single probabilistic retrieval model. This new approach is designed primarily for Intranet environments, where it is reasonable to assume that resource providers are relatively homogeneous and can adopt the same kind of search engine. Experiments demonstrate that this new, integrated approach is at least as effective as the prior state-of-the-art in distributed IR.
A New Probabilistic Model for Title Generation.
Title generation is a complex task involving  both natural language understanding and  natural language synthesis. In this paper, we  propose a new probabilistic model for title  generation. Different from the previous  statistical models for title generation, which  treat title generation as a generation process  that converts the `document representation&#039;  of information directly into a `title  representation&#039; of the same information, this  model introduces a hidden state called  `information source&#039; and divides title  generation into two steps, namely the step of  distilling the `information source&#039; from the  observation of a document and the step of  generating a title from the estimated  `information source&#039;. In our experiment, the  new probabilistic model outperforms the  previous model for title generation in terms  of both automatic evaluations and human  judgments.
Using a probabilistic source model for comparing images.
In this paper, we propose a probabilistic model for image retrieval. To obtain the similarity between the query image I Q and any image I ’ in the collection, this model computes the probability of generating the image I ’ given the observation of the query image I Q. We compared our probabilistic model for image retrieval with a color histogram based image retrieval method and the IBM QBIC image search engine. The evaluation used the 11-hour video retrieval collection (80000 extracted images) and associated queries from the 2001 TREC-10 information retrieval evaluations. The experimental results show that the probabilistic model dramatically outperforms the color histogram based image retrieval method and the IBM QBIC image search engine by 40%. 1.
A Probabilistic Model for Camera Zoom Detection.
Camera motion detection is essential for automated video analysis. We propose a new probabilistic model for detecting zoom-in/zoom-out operations. The model uses EM to estimate the probability of a zoom versus a nonzoom operation from standard MPEG motion vectors. Traditional methods usually set an empirical threshold after deriving parameters proportional to zoom, pan, rotate and tilt. In contrast, our probabilistic model has a solid probabilistic foundation and a clear, simple probability threshold. Experiments show that this probabilistic model significantly out-performs a baseline parametric method for zoom detection in both precision and recall.
Multi%2Dmodal information retrieval from broadcast video using OCR and speech recognition.
We examine multi-modal information retrieval from broadcast video where text can be read on the screen through OCR and speech recognition can be performed on the audio track. OCR and speech recognition are compared on the 2001 TREC Video Retrieval evaluation corpus. Results show that OCR is more important that speech recognition for video retrieval. OCR retrieval can further improve through dictionary-based post-processing. We demonstrate how to utilize imperfect multi-modal metadata results to benefit multi-modal information retrieval.
Meta%2DClassification of Multimedia Classifiers.
Combining multiple classifiers is of particular interest in the multimedia systems, since there is usually data of very different types/modalities that should be mined or analyzed. Our wearable &#039;experience collection&#039; system unobtrusively records the wearer&#039;s conversation, recognizes the face of the dialog partner and remembers his/her voice. When the system sees the same person&#039;s face or hears the same voice it can then use a summary of the last conversation with this person to remind the wearer. To correctly identify a person from a mixture of video and audio stream, classification judgments from individual modality classifiers must be combined effectively to yield a more accurate decision. To address the problems of combination strategy in previous studies, a meta-classification strategy using Support Vector Machine is proposed. Preliminary results show that combining different face recognition and speaker identification technology by meta-classification is dramatically more effective than weighted interpolation. Meta-classification is general enough to be applied to any application that needs to combine multiple classifiers without much modification.
Learning with Multiple Labels.
In this paper, we study a special kind of learning problem in which  each training instance is given a set of (or distribution over)  candidate class labels and only one of the candidate labels is the  correct one. Such a problem can occur, e.g., in an information  retrieval setting where a set of words is associated with an image,  or if classes labels are organized hierarchically. We propose a  novel discriminative approach for handling the ambiguity of class  labels in the training examples. The experiments with the proposed  approach over five different UCI datasets show that our approach is  able to find the correct label among the set of candidate labels and  actually achieve performance close to the case when each training  instance is given a single correct label. In contrast, naive methods  degrade rapidly as more ambiguity is introduced into the labels.
Language model for IR using collection information.
early age of IR where documents are represented by the controlled vocabulary. In this paper, we explore the usage of meta-data information under the framework of language model. We present a new language model that is able to take advantage of the category information for documents to improve the retrieval accuracy. We compare the new language model with the traditional language model over the TREC4 dataset where the collection information for documents is obtained using the kmeans clustering method. The new language model outperforms the traditional language model, which verifies our statement.
Title language model for information retrieval.
In this paper, we propose a new language model, namely, a title language model, for information retrieval. Different from the traditional language model used for retrieval, we define the conditional probability P(Q|D) as the probability of using query Q as the title for document D. We adopted the statistical translation model learned from the title and document pairs in the collection to compute the probability P(Q|D). To avoid the sparse data problem, we propose two new smoothing methods. In the experiments with four different TREC document collections, the title language model for information retrieval with the new smoothing method outperforms both the traditional language model and the vector space model for IR significantly.
Video Classification and Retrieval with the Informedia Digital Video Library System.
This paper is organized in three parts. The first part details some of the lower level shot classification work, the second part describes the ‘manual ’ retrieval systems while the last section details the interactive retrieval system for the Carnegie Mellon University TREC Video Retrieval Track runs. The description of the data can be found elsewhere in the proceedings of the 2002 TREC conference video track overview. Classification In the TREC02 video track, one of the main tasks is to detect various semantic features concepts such as “Indoor/Outdoor”, “People ” etc. This part contains the description of the classification tasks. We submitted runs for the following classification concepts in the TREC 2002 Video Track. To obtain training data, we manually annotated each I-frame of the 23.26 hours feature development collection for each category. a. Outdoors: Segment contains a recognizably outdoor location, i.e., one outside of buildings. Should exclude all scenes that are indoors or are close-ups of objects (even if the objects are outdoor). b. Indoors: Segment contains a recognizably indoor location, i.e., inside a building. Should exclude all scenes that are outdoors or are close-ups of objects (even if the objects are indoor c. Cityscape: Segment contains a recognizably city/urban/suburban setting. d. Monologue: an event in which a single person is at least partially visible and speaks for a long time without
Title Generation Using a Training Corpus.

Learning to Select Good Title Words An New Approach based on Reverse Information Retrieval.
In this paper, we show how we can learn to  select good words for a document title. We  view the problem of selecting good title words  for a document as a variant of an Information  Retrieval problem. Each title word is treated as  a &#034;document&#034; and selection of appropriate title  words as finding relevant &#034;documents&#034;. Based  on our training collection consisting of 40,000  document and title pairs, we learn the  &#034;document&#034; representations for all the title  words and apply these learned representations  to select appropriate title words over 10,000  test documents. Compared to other learning  approaches, namely K nearest neighbor  approach, a Nave Bayesian approach and a  variant of a machine translation model, we  find that our approach is significantly better as  indicated by the F1 metric.
Title Generation for Machine%2DTranslated Documents.
In this paper, we present and compare automatically generated titles for machine-translated documents using several different statistics-based methods. A Naïve Bayesian, a K-Nearest Neighbour, a TF-IDF and an iterative Expectation-Maximization method for title generation were applied to 1000 original English news documents and again to the same documents translated from English into Portuguese, French or German and back to English using SYSTRAN. The AutoSummarization function of Microsoft Word was used as a base line. Results on several metrics show that the statisticsbased methods of title generation for machinetranslated documents are fairly language independent and title generation is possible at a level approaching the accuracy of titles generated for the original English documents. 1.
Probabilistic Combination of Content and Links.
Previous research has shown that citations and hypertext links can be usefully combined with document content to improve retrieval. Links can be used in many ways, e.g., link topology can be used to identify important pages, anchor text can be used to augment the text of cited pages, and activation can be spread to linked pages. This paper introduces a probabilistic model that integrates content matching and these three uses of link information in a single unified framework. Experiments with a web collection show benefits for link information especially for general queries.
Meta%2Dscoring Automatically Evaluating Term Weighting Schemes in IR without Precision%2DRecall.
In this paper, we present a method that can automatically evaluate performance of different term weighting schemes in information retrieval without resorting to precision-recall based on human relevance judgments. Specifically, the problem is: given two document-term matrixes generated from two different term weighting schemes, can we tell which term weighting scheme will performance better than the other? We propose a meta-scoring function, which takes as input the document-term matrix generated by some term weighting scheme and computes a “goodness ” score from the documentterm matrix. In our experiments, we found out that this score is highly correlated with the precision-recall measurement for all the collections and term weighting schema we tried. Thus, we conclude that our meta-scoring function can be a substitute for the precision-recall measurement that needs relevance judgments of human subject. Furthermore, this meta-scoring function is not limited only to text information retrieval can be applied to fields such as image and DNA retrieval.
Video Retrieval with the Informedia Digital Video Library System.
information extraction from video and audio content. Over a terabyte of online data was collected, with automatically generated metadata and indices for retrieving videos from this library. The architecture for the project was based on the premise that real-time constraints on library and associated metadata creation could be relaxed in order to realize increased automation and deeper parsing and indexing for identifying the library contents and breaking it into segments. Library creation was an offline activity, with library exploration by users occurring online and making use of the generated metadata and segmentation. The goal of the Informedia interface was to enable quick access to relevant information in a digital video library, leveraging from derived metadata and the partitioning of the video into small segments. Figure 1 shows the IDVLS interface following a query. In this figure, a set of results is displayed at the bottom. The display includes a window containing a headline, and a pictorial menu of video segments each represented with a thumbnail image at approximately  resolution of the video in the horizontal and vertical dimensions. The headline window automatically pops up whenever the mouse is positioned over a result item; the headline window for the first result is shown. IDVLS also supports other ways of navigating and browsing the digital video library. These interface features were essential to deal with the ambiguity of the derived data generated by speech recognition,

Data Analysis for a Multimedia Library.


